#define abs(a) (((a) > 0) ? (a) : (-(a)))

// step 0# 计算数组所有元素之和
int sum(int *nums, int numsSize) {
    int sum = 0;
    for(int i = 0; i < numsSize; ++i) {
        sum += nums[i];
    }
    return sum;
}

// step 1# 排序比较函数：按元素的绝对值从大到小排序
int cmp(const void* v1, const void* v2) {
    return abs(*(int*)v2) - abs(*(int*)v1);
}

int largestSumAfterKNegations(int* nums, int numsSize, int k) {
    // step 2# 先按绝对值从大到小排序：大数优先操作，最大化对总和的影响
    qsort(nums, numsSize, sizeof(int), cmp);

    // step 3# 遍历数组，尝试优先把负数变正
    for(int i = 0; i < numsSize; ++i) {
        // step 3.1# 当前元素为负数，且还有剩余k次取反机会
        if(nums[i] < 0 && k > 0) {
            nums[i] *= -1;  // step 3.2# 把负数取反
            --k;            // step 3.3# 用掉一次操作
        }
    }

    // step 4# 如果k还剩奇数次（说明最终一定要反一次），则反转绝对值最小的那个元素
    if(k % 2 == 1) {
        // 由于排序是按绝对值排的，末尾是绝对值最小的元素
        nums[numsSize - 1] *= -1;
    }

    // step 5# 返回数组总和
    return sum(nums, numsSize);
}
